package com.example.question.dp.dp2;

import java.util.Arrays;
import java.util.List;

/**
 * @Date 2023-07-25
 * @Author Jonathan
 */
public class Code14_139 {
    public static void main(String[] args) {
        Code14_139 code = new Code14_139();
        String s = "applepenapple";
        List<String> list = Arrays.asList("apple", "pen");
        System.out.println("code.wordBreak(s, list) = " + code.wordBreak(s, list));
    }


    public boolean wordBreak1(String s, List<String> wordDict) {
        // dp[i]表示前i个字符组成的字符是否可以被wordDict中字符组合而成
        Boolean[] dp = new Boolean[s.length() + 1];
        // 初始条件
        dp[0] = true;

        // 状态转移
        for (int i = 1; i < s.length(); i++) {
            for (String word : wordDict) {
                int wordLen = word.length();
                if (i >= wordLen && s.substring(i - wordLen, i).equals(word)) {
                    dp[i] = dp[i] || dp[i - wordLen];
                }
            }
        }
        return dp[s.length()];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict, 0, new Boolean[s.length()]);
    }

    /**
     * 以i开头的字串 是否可以拆分
     */
    private boolean dfs(String s, List<String> wordDict, int index, Boolean[] memo) {
        if (index == s.length()) {
            return true;
        }
        if (memo[index] != null) {
            return memo[index];
        }
        boolean res = false;
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            // 剪枝
            if (!wordDict.contains(str)) {
                continue;
            }
            //
            boolean dfs = dfs(s, wordDict, i + 1, memo);
            res = res || dfs;
        }
        memo[index] = res;
        return res;
    }
}
